package com.ryujung.binary_tree.leetcode_105;
/*
 * @lc app=leetcode.cn id=105 lang=java
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

// @lc code=start

//Definition for a binary tree node.

class Solution {

    public static void main(String[] args) {
        // TreeNode node = new TreeNode(1, new TreeNode(2, new TreeNode(4, null, null),
        // null),
        // new TreeNode(3, null, null));
        // System.out.println(preOrder(node));
        // System.out.println(inOrder(node));
        // TreeNode result = buildTree(new int[] { 3, 9, 20, 15, 7 }, new int[] { 9, 3,
        // 15, 20, 7 });
        TreeNode result = buildTree(new int[] { 1, 2, 3 }, new int[] { 3, 2, 1 });
        System.out.println(preOrder(result));
        System.out.println(inOrder(result));
        System.out.println(postOrder(result));
    }

    /**
     * 前序遍历：先遍历根节点，再遍历左、右子树
     * 中序遍历：先遍历左子树，在遍历根节点、在遍历右子树
     * 后序遍历：先遍历左子树，再遍历右子树，最后是根节点
     * 
     * 本题特点：
     * 1. 前序遍历的第一个元素为根节点
     * 2. 提示：前序和中序遍历中没有重复元素，即：中序遍历的根节点是可以唯一辨认的
     * 3. 中序遍历中找到根节点元素，则左边为左子树，右边为右子树
     * 4. 根据以上规律，进行递归即可
     * 
     * Your runtime beats 7.87 % of java submissions
     * Your memory usage beats 6.17 % of java submissions (72.7 MB)
     */
    public static TreeNode buildTreePass1(int[] preorder, int[] inorder) {
        if (preorder.length < 1) {
            return null;
        }

        TreeNode rootNode = new TreeNode(preorder[0], null, null);
        int len = preorder.length;
        if (len == 1) {
            return rootNode;
        }

        // 定位中序遍历的根节点位置
        int middle = 0;
        while (inorder[middle] != rootNode.val) {
            middle++;
        }
        // 存在左树，递归构造左子树
        // 左树length:m ,前序边界:[1,m-1+1],中序边界:[0,m] (include left, except right)
        TreeNode leftNode = buildTreePass1(Arrays.copyOfRange(preorder, 1, middle + 1),
                Arrays.copyOfRange(inorder, 0, middle));

        // rightTree: len: len-m-1 pre[length-m,length],in[m+1,length]
        TreeNode rightNode = buildTreePass1(Arrays.copyOfRange(preorder, middle + 1, len),
                Arrays.copyOfRange(inorder, middle + 1, preorder.length));
        rootNode.left = leftNode;
        rootNode.right = rightNode;
        return rootNode;
    }

    /**
     * 思路2：
     * 不对原数组进行拷贝，根据角标进行递归即可
     */
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        int rootIndex = 0;
        while (inorder[rootIndex] != preorder[0]) {
            rootIndex++;
        }
        int len = preorder.length;
        TreeNode node = new TreeNode(preorder[0]);
        // 中序：rootIndex为根，0~rootIndex-1为左子树（长度rootIndex），rootIndex+1~len-1为右子树（长度len-rootIndex-1）；
        // 前序：0为根，1~rootIndex为左子树，rootIndex+1~len-1为右子树
        node.left = helper(preorder, 1, rootIndex, inorder, 0, rootIndex - 1);
        node.right = helper(preorder, rootIndex + 1, len - 1, inorder, rootIndex + 1, len - 1);

        return node;
    }

    private static TreeNode helper(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
        if (preLeft > preRight) {
            return null;
        }
        if (preLeft == preRight) {
            return new TreeNode(preorder[preLeft]);
        }

        TreeNode root = new TreeNode(preorder[preLeft]);
        int rootIndex = inLeft;
        int leftLen = 0;
        while (inorder[rootIndex] != preorder[preLeft]) {
            rootIndex++;
            leftLen++;
        }
        int len = preRight - preLeft + 1;
        root.left = helper(preorder, preLeft + 1, preLeft + leftLen, inorder, inLeft, inLeft + leftLen - 1);
        root.right = helper(preorder, preLeft + leftLen + 1, preRight, inorder, rootIndex + 1, preLeft + len - 1);
        return root;
    }

    // 前序遍历
    public static List<Integer> preOrder(TreeNode node) {
        if (node == null)
            return Collections.emptyList();

        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(node.val);
        list.addAll(preOrder(node.left));
        list.addAll(preOrder(node.right));
        return list;
    }

    // 中序遍历
    public static List<Integer> inOrder(TreeNode node) {
        if (node == null)
            return Collections.emptyList();

        LinkedList<Integer> list = new LinkedList<>();

        list.addAll(inOrder(node.left));
        list.add(node.val);
        list.addAll(inOrder(node.right));
        return list;
    }

    // 后序遍历
    public static List<Integer> postOrder(TreeNode node) {
        if (node == null)
            return Collections.emptyList();

        LinkedList<Integer> list = new LinkedList<>();
        list.addAll(postOrder(node.left));
        list.addAll(postOrder(node.right));
        list.add(node.val);
        return list;
    }

    // 序列化
    public static Integer[] serialize(TreeNode node) {
        if (node == null)
            return new Integer[0];

        LinkedList<Integer> list = new LinkedList<>();
        list.add(node.val);
        list.addAll(preOrder(node.left));
        list.addAll(preOrder(node.right));
        return list.toArray(new Integer[list.size()]);
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
// @lc code=end
